<?php
/**
 * @title 1536. 排布二进制网格的最少交换次数 - 最近匹配
 * @author start2004
 */


class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function minSwaps($grid) {
        /**
         * @since 2021-08-10 长度
         */
        $n = count($grid);

        /**
         * @since 2021-08-10 简化, 每行改成, 从尾部开始连续零的数量
         */
        $numArray = [];
        for ($i=0; $i<$n; $i++){
            $num = 0;
            for ($j=$n-1; $j>=0; $j--){
                if($grid[$i][$j] == 0){
                    $num++;
                } else {
                    break;
                }
            }
            $numArray[] = $num;
        }

        /**
         * @since 2021-08-10 移动次数
         */
        $result = 0;

        /**
         * @since 2021-08-10 从高到低
         */
        for ($i=0; $i<=$n-2; $i++){
            /**
             * @since 2021-08-10 需要0的数量
             */
            $needZeroCnt = $n-$i-1;

            /**
             * @since 2021-08-10 找到最近符合条件的行
             */
            $j = 0;
            $find = false;
            foreach ($numArray as $k=>$v){
                /**
                 * @since 2021-08-10 找到符合条件
                 */
                if($numArray[$k] >= $needZeroCnt){
                    unset($numArray[$k]);
                    $result += $j;
                    $find = true;
                    break;
                } else {}
                $j++;
            }

            /**
             * @since 2021-08-10 没有找到
             */
            if($find === false){
                return -1;
            } else {}
        }

        /**
         * @return
         */
        return $result;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.03_2.php
 */
$datas = [
    [[0,0,1],[1,1,0],[1,0,0]], // 3
    [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]], // -1
    [[1,0,0],[1,1,0],[1,1,1]], // 0
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->minSwaps($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
